import collections
from typing import List


class Trie:
    class _Node:
        def __init__(self):
            self.value = None
            self.count = 0
            self.children = {}

        def __contains__(self, ch):
            return ch in self.children

        def __getitem__(self, ch):
            return self.children[ch]

    def __init__(self):
        self.root = self._Node()

    def add(self, word):
        node = self.root
        for ch in word:
            if ch not in node:
                node.children[ch] = self._Node()
            node.count += 1
            node = node.children[ch]
        node.value = word


class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        words.sort(key=lambda x: (len(x), x))

        trie = Trie()

        ans = []

        for word in words:
            size = len(word)

            # print("【当前词】", word)

            visited = {0}
            find = collections.deque([0])

            while find:
                # print(find, visited)
                idx = find.pop()
                node = trie.root
                for i in range(idx, size):
                    if word[i] in node:
                        node = node[word[i]]
                    else:
                        break

                    if node.value:
                        # print("找到词:", node.value)
                        if i + 1 not in visited:
                            find.append(i + 1)
                            visited.add(i + 1)

                if size in visited:
                    break

            if size in find:
                ans.append(word)

            trie.add(word)

        return ans


if __name__ == "__main__":
    # ["catsdogcats","dogcatsdog","ratcatdogcat"]
    print(Solution().findAllConcatenatedWordsInADict(
        ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]))
